package com.mccken.practice.top100.Top_30$.Top_30;

import java.util.HashMap;
import java.util.Map;

import com.mccken.practice.top100.Node;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-02-28 17:50
 **/
public class CopyRandomList {
	Map<Node, Node> cachedNode = new HashMap<>();

	public Node copyRandomList(Node head) {
		if (head == null) {
			return null;
		}
		
		// 创建节点
		for (Node node = head; node != null; node = node.next.next) {
			Node newNode = new Node(node.val);
			newNode.next = node.next;
			node.next = newNode;
		}

		for (Node node = head; node != null; node = node.next.next) {
			Node newNode = node.next;
			newNode.random = node.random != null ? node.random.next : null;
		}
		
		Node newHead = head.next;
		// 脱链。next
		for (Node node = head; node != null; node = node.next) {
			Node newNode = node.next;	
			node.next = node.next.next;
			newNode.next = newNode.next != null ? newNode.next.next : null;
		}
		
		return newHead;
	}
	public Node copyRandomList2(Node head) {
		if (head == null) {
			return null;
		}
		if (!cachedNode.containsKey(head)) {
			Node newNode = new Node(head.val);
			cachedNode.put(head, newNode); 	
			newNode.next = copyRandomList2(head.next);
			newNode.random = copyRandomList2(head.random);
		}
		return cachedNode.get(head);
	}


	public static void main(String[] args) {
		// [[7,null],[13,0],[11,4],[10,2],[1,0]]

	}
}
